725. Split Linked List in Parts

https://leetcode.com/problems/split-linked-list-in-parts/

題目解釋

你會得到一組鏈結串列的頭head，還有一個數字k

請把這組鏈結串列拆成k個鏈結串列，且要符合下列三個規則

1. 相鄰的兩段鏈結串列長度不能超過1個
2. 前面的鏈結長度必須大於等於後面的鏈結長度
3. 數字並須要保有原來的順序

example

解法

我們可以把原本的鏈結切成k段，或是做出k個新的鏈結

不論如何我們都需要先知道鏈結的長度有多長，所以我們先全部輪過一遍找出長度N

接著，我們要找出每一段分別要放幾個節點，並符合上面提到的規則

以k=3, N=10作為例子，我們的鏈結長度就會分別是4,3,3

也就是每個鏈結長度是N//3，但是前N%3個鏈結的節點會多一個

知道長度之後我們就知道要在哪斷開鏈結了

程式碼

class Solution:
    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:
        
        node = head
        N = 0
        while node:
            N += 1
            node = node.next
        
        D = N // k
        M = N % k
        
        ans = []
        node1, node2 = ListNode(head), head
        # node1是留來斷開鏈結的
        for i in range(M):
            root = node2
            for i in range(D+1):
                if node2:
                    node1 = node2
                    node2 = node2.next
            
            node1.next = None
            ans.append(root)
                
        node1, node2 = ListNode(node2), node2
        for i in range(k - M):
            root = node2
            for i in range(D):
                if node2:
                    node1 = node2
                    node2 = node2.next
            
            node1.next = None
            ans.append(root)
        
        return ans

上面的程式碼真的醜

稍微好看一點的版本

class Solution:
    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:
        
        node = head
        N = 0
        while node:
            N += 1
            node = node.next
        
        D = N // k
        M = N % k
        
        size = [D+1] * M + [D] * (k - M)
        ans = []
        
        node = head
        for i in size:
            root = node
            for j in range(i-1):
                if node:
                    node = node.next
                
            ans.append(root)
            if node:
                node.next ,node = None, node.next
        
        return ans

閒聊

鏈結是一種網羅，我們要斷開魂節